/*
 * @lc app=leetcode.cn id=1036 lang=cpp
 *
 * [1036] 逃离大迷宫
 */
#include "include.h"
// @lc code=start
// struct hash_fn {
//         std::size_t operator() (const pair<int, int>& o) {
//             auto& [x, y] = o;
//             auto fn = hash<long long>();
//             return fn((long long)x << 20 | y);
//         }
//     };
std::size_t hashFunc(const pair<int, int>& o) {
            auto& [x, y] = o;
            auto fn = hash<long long>();
            return fn((long long)x << 20 | y);
        }
class Solution {
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        std::pair start(source[0], source[1]);
        std::pair end(target[0], target[1]);

        if (start == end) {return true;}

        // record blocked cells
        for (auto& block : blocked) {
            blockHash.emplace(block[0], block[1]);
        }

        if (!checkOneside(start, end)) return false;
        if (!checkOneside(end, start)) return false;
        return true;
    }
private:
    bool checkOneside(std::pair<int, int>& start, std::pair<int, int>& end) {
        visitHash.clear();
        visitHash.emplace(start.first, start.second);

        std::queue<std::pair<int, int>> cellQueue;
        cellQueue.push(start);

        int checkedCellCounter = 1;

        while (!cellQueue.empty()) {
            auto currentCell = cellQueue.front();
            cellQueue.pop();

            for (int i=0;i<4;++i) {
                int x = currentCell.first + directions[i][0];
                int y = currentCell.second + directions[i][1];

                if ((x < 0 or x >= 1000000) or (y < 0 or y >= 1000000)) continue;
                std::pair neiborCell(x, y);
                if (blockHash.find(neiborCell) != blockHash.end()) continue;
                if (visitHash.find(neiborCell) != visitHash.end()) continue;
                if (neiborCell == end) {
                    // printf("f0 c %d\n", checkedCellCounter);
                    return true;}

                checkedCellCounter += 1;
                if (visitHash.size() > maxCellCheck) {
                    // printf("f1 c %d b %zu v %zu\n", checkedCellCounter, blockHash.size(), visitHash.size());
                    return true;}

                visitHash.emplace(x, y);
                cellQueue.push(neiborCell);
            }
            // check inside 0 <= x, y < 1e6
            // check blocked
            // check visited
            // check if it is target
        }
        return false;
    }
private:
    const int n = 200;
    const int maxCellCheck = n*(n-1)/2;
    const int directions[4][2] = {
        {0, -1},
        {0, 1},
        {-1, 0},
        {1, 0},
    };
    std::unordered_set<std::pair<int, int>, std::size_t(*)(const pair<int, int>& o)> blockHash{0, hashFunc};
    std::unordered_set<std::pair<int, int>, std::size_t(*)(const pair<int, int>& o)> visitHash{0, hashFunc};
    // maybe need learn:
    // Astar + hash
    // quarter tree map
};
// @lc code=end
// [[10,9],[9,10],[10,11],[11,10]]\n[0,0]\n[10,10]
// [[100059,100063],[100060,100064],[100061,100065],[100062,100066],[100063,100067],[100064,100068],[100065,100069],[100066,100070],[100067,100071],[100068,100072],[100069,100073],[100070,100074],[100071,100075],[100072,100076],[100073,100077],[100074,100078],[100075,100079],[100076,100080],[100077,100081],[100078,100082],[100079,100083],[100080,100082],[100081,100081],[100082,100080],[100083,100079],[100084,100078],[100085,100077],[100086,100076],[100087,100075],[100088,100074],[100089,100073],[100090,100072],[100091,100071],[100092,100070],[100093,100069],[100094,100068],[100095,100067],[100096,100066],[100097,100065],[100098,100064],[100099,100063],[100098,100062],[100097,100061],[100096,100060],[100095,100059],[100094,100058],[100093,100057],[100092,100056],[100091,100055],[100090,100054],[100089,100053],[100088,100052],[100087,100051],[100086,100050],[100085,100049],[100084,100048],[100083,100047],[100082,100046],[100081,100045],[100080,100044],[100079,100043],[100078,100044],[100077,100045],[100076,100046],[100075,100047],[100074,100048],[100073,100049],[100072,100050],[100071,100051],[100070,100052],[100069,100053],[100068,100054],[100067,100055],[100066,100056],[100065,100057],[100064,100058],[100063,100059],[100062,100060],[100061,100061],[100060,100062]]\n[100079,100063]\n[999948,999967]